package find;

public class Ex4 {
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int m = nums1.length, n = nums2.length, len = m + n; 
    
            if (m > n) {
                return findMedianSortedArrays(nums2, nums1);
            }
    
            //求出联动的两个分割线，其中一个分割线确定之后，另一个随之确定
            //这是因为中位数肯定是中间的一两个数，因此中间位置就是(m + n + 1) / 2 == i + j
    
            //只看第一个的i
            int lo = 0, hi = m - 1;
            int i, j;
            while (lo <= hi) {
                i = (lo + hi) / 2;
                j = (len + 1) / 2 - i;
                // int lu = i == 0 ? Integer.MAX_VALUE : nums1[i - 1];
                // int ru = i == m - 1 ? Integer.MAX_VALUE : nums[i + 1];
                // int lb = j == 0 ? Integer.MAX_VALUE : nums2[j - 1];
                // int rb = i == m - 1 ? Integer.MAX_VALUE : nums[j + 1];
                //将上面的逻辑简化一点：
                //真正需要的是综合两个数组的上半部分最大值maxLeft和下半部分最小值minRight
                if (i != 0 && j != n - 1 && nums1[i - 1] > nums2[j]) {
                    hi = i - 1; //i的位置太靠右了
                    //i偏右，导致左边最大值即将大于右边最小值
                } else if  (i != m - 1 && j != 0 && nums1[i] < nums2[j - 1]) {
                    lo = i + 1;
                } else {
                     int maxLeft = 0, minRight = 0;
                    if (i == 0) {
                        //画个图就能理解了，关键是明白i,j其实是综合数组的中点。
                        maxLeft = nums2[j - 1];
                    } else if (j == 0) {  
                        maxLeft = nums1[i - 1];
                    } else {
                        maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
                    }
                    if (i == m - 1) {
                        minRight = nums2[j - 1];
                    } else if (j == n - 1) {
                        minRight = nums1[i + 1];
                    } else {
                        minRight = Math.min(nums1[i + 1], nums2[j + 1]);
                    }
                    //取中点时加一可以使得奇数时左边必然多一个
                    return (len % 2 == 0) ? (double)(minRight + maxLeft) / 2.0 : maxLeft;
                }
               
            }
            return -1;
        }
    }
}
